package com.arithmeticEveryDay.divideAndConquer;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.StringTokenizer;

/*

给定n(1<=n<=100000)个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n],
求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时定义子段和为0，
依此定义，所求的最优值为：Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n。
例如，当（a[1],a[2],a[3],a[4],a[5],a[6]）=(-2,11,-4,13,-5,-2)时，最大子段和为20.

6
-2 11 -4 13 -5 -2

分治策略：
最大子段和的结果子段的分布有三种：1、begin ~ mid-1, 2、mid ~ end, 3、包含mid-1和mid的子段

 */
public class MaxSubsegmentSum {
    
    static InOut3 io = new InOut3();
    int n;
    int[] arr;
    int maxSum;
    public MaxSubsegmentSum() {
        n = io.nextInt();
        arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = io.nextInt();
        }
        maxSum = divide(0, n-1);
    }
    
    private int divide(int begin, int end) {
        // TODO Auto-generated method stub
        if (begin == end) {
            return arr[begin] > 0 ? arr[begin] : 0;
        }
        int mid = (end + begin) / 2;
        int leftSubSum = divide(begin, mid);
        int rightSubSum = divide(mid + 1, end);
        int centerSubSum = 0;
        int tempSum = 0;
        for (int i = mid; i >= begin; i--) {
            tempSum += arr[i];
            if (tempSum > centerSubSum) {
                centerSubSum = tempSum;
            }
        }
        tempSum = centerSubSum;
        for (int i = mid + 1; i <= end; i++) {
            tempSum += arr[i];
            if (tempSum > centerSubSum) {
                centerSubSum = tempSum;
            }
        }
        int max = Math.max(centerSubSum, Math.max(leftSubSum, rightSubSum));
        io.out.println(begin + ", " + end + ", " + max + ", " + centerSubSum);
        return max;
    }


    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MaxSubsegmentSum m = new MaxSubsegmentSum();
        io.out.print(m.maxSum);
        io.out.flush();
    }
}
class InOut3 {
    BufferedReader br;
    StringTokenizer tok;
    PrintWriter out;
    InOut3() {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(new OutputStreamWriter(System.out));
    }
    public boolean hasNext() {
        while (tok == null || !tok.hasMoreElements()) {
            try {
                tok = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                // TODO Auto-generated catch block
                return false;
            }
        }
        return true;
    }
    public String next() {
        if (hasNext()) {
            return tok.nextToken();
        }
        return null;
    }
    public int nextInt() {
        return Integer.parseInt(next());
    }
}
